import collections
import heapq

class Solution(object):
    def maximumScore(self, scores, edges):
        """
        :type scores: List[int]
        :type edges: List[List[int]]
        :rtype: int
        """
        d = collections.defaultdict(list)
        c = {}
        n = len(scores)
        for edge in edges:
            d[edge[0]].append([scores[edge[1]], edge[1]])
            d[edge[1]].append([scores[edge[0]], edge[0]])
        for i in range(n):
            if i in d:
                c[i] = heapq.nlargest(3, d[i])
        max_score = -1
        for edge in edges:
            base_score = scores[edge[0]] + scores[edge[1]]
            c1 = c[edge[0]]
            c2 = c[edge[1]]
            value = -1
            for p1 in c1:
                for p2 in c2:
                    if p1[1] != edge[1] and p1[1] != p2[1] and p2[1] != edge[0]:
                        value = max(value, p1[0] + p2[0])
            if value > 0:
                max_score = max(max_score, base_score + value)
        return max_score





data = Solution()
scores = [5, 2, 9, 8, 4]
edges = [[0, 1], [1, 2], [2, 3], [0, 2], [1, 3], [2, 4]]
print(data.maximumScore(scores, edges))
scores = [9, 20, 6, 4, 11, 12]
edges = [[0, 3], [5, 3], [2, 4], [1, 3]]
print(data.maximumScore(scores, edges))
